package 面试经典150题.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author tmh
 * @date 2024/6/6 19:59
 * @description
 */
public class T15三数之和 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //如果数组里面不足三个数，直接返回空数组
        if (nums.length < 3) {
            return result;
        }
        //数组进行排序
        Arrays.sort(nums);
        //遍历数组中的每个元素
        for (int i = 0; i < nums.length; i++) {
            //如果遍历的起始元素就大于0了，那么就直接退出
            if (nums[i] > 0) {
                break;
            }
            //去重，当起始的值等于前一个元素，那么得到的结果将会和前一次相同
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            int l = i + 1;
            int r = nums.length - 1;
            //当l不等于r的时候继续遍历
            while (l < r) {
                int sum = nums[i]+nums[l]+nums[r];
                if(sum==0){
                    result.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    //对左右指针进行一个去重
                    //先对左面的指针进行一个去重
                    while (l<r&&nums[l]==nums[l+1]){
                        l++;
                    }
                    while (l<r&&nums[r]==nums[r-1]){
                        r--;
                    }
                    //将左面的指针右面移动
                    l++;
                    //将右面的指针左面移动
                    r--;
                }else {
                    //如果结果小于0，那么就把左面的指针往后面移动
                    if (sum>0){
                        r--;
                    }
                    //如果结果大于0，那么就把右面的指针往前面移动
                    if(sum<0){
                        l++;
                    }
                }
            }
        }
        return result;
    }
}
